package com.tgy.cmp;

import com.tgy.Sort;

/**
 * @Author: tgy
 * @Date: 2020-10-29 17:50
 */
public class QuickSort04<E> extends Sort<E> {


    @Override
    protected void sort() {

        sort(0,elements.length);
    }

    private void sort(int begin, int end) {

        int left = begin, right = end - 1;

        E base = elements[begin];
        while (left < right) {

            while (left < right && compare(base,elements[right]) < 0) {

                right--;
            }

            if (left < right) {

                elements[left++] = elements[right];
            }

            while (left < right && compare(base,elements[left]) > 0) {

                left++;
            }

            if (left < right) {

                elements[right--] = elements[left];
            }
        }

        elements[left] = base;

        if (begin + 1 < left ) {

            sort(begin,left);
        }

        if (end - left > 2) {

            sort(left + 1,end);
        }

    }
}
